package org.example.algorithm.str;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定m个不重复的字符 [a, b, c, d]，以及一个长度为n的字符串tbcacbdata， 问能否在这个字符串中找到一个长度为m的连续子串，
 * 使得这个子串刚好由上面m个字符组成，顺序无所谓，返回任意满足条件的一个子串的起始位置，未找到返回-1。比如上面这个例子，返回3
 */
public class FindSubStringSolution {

    public static void main(String[] args) {
        Character[] charArr = {'t', 'a'};
        String str = "tbcacbdata";
        int index = findSubStringEasy(str, charArr);
        System.out.println(index);
    }

    private static int findSubStringEasy(String str, Character[] charArr) {
        Map<Character, Integer> charMap = buildMap(charArr);
        for (int j=0;j<str.length();j++) {
            Map<Character, Integer> compareMap = new HashMap<>();
            boolean flag = true;
            for (int i=0;i<charArr.length;i++) {
                if (!charMap.containsKey(str.charAt(i+j))) {
                    flag = false;
                    break;
                }
                if (compareMap.containsKey(str.charAt(i+j))) {
                    flag = false;
                    break;
                } else {
                    compareMap.put(str.charAt(i+j), 1);
                }
            }
            if (flag) {
                return j;
            }
        }
        return -1;
    }

    private static Map<Character, Integer> buildMap(Character[] charArr) {
        Map<Character, Integer> charMap = new HashMap<>();
        for (Character character: charArr) {
            charMap.put(character, 1);
        }
        return charMap;
    }

    //该实现重复子串也可以查找
    private static int findSubString(String str, Character[] charArr) {
        //初始化匹配结构
        Map<Character, int[]> compareMap = resetMatchMap(charArr);
        int matchSize = 0;
        for (int j=0;j<str.length();j++) {
            if (compareMap.containsKey(str.charAt(j))) {
                int[] charInfo = compareMap.get(str.charAt(j));
                if (charInfo[0] >= 1) {
                    charInfo[0]--;
                    if (charInfo[1] == -1) {
                        charInfo[1] = j;
                    }
                    matchSize++;
                    if (matchSize == charArr.length) {
                        return j - (charArr.length - 1);
                    }
                } else {
                    //匹配某个字符大于预期值
                    matchSize = 0;
                    j = charInfo[1];
                    compareMap = resetMatchMap(charArr);
                }
            } else {
                matchSize = 0;
                compareMap = resetMatchMap(charArr);
            }
        }
        return -1;
    }

    private static Map<Character, int[]> resetMatchMap(Character[] charArr) {
        Map<Character, int[]> matchMap = new HashMap<>();
        for (Character character : charArr) {
            if (matchMap.containsKey(character)) {
                int[] charInfo = matchMap.get(character);
                charInfo[0]++;
                matchMap.put(character, charInfo);
            } else {
                int[] charInfo = {1, -1};
                matchMap.put(character, charInfo);
            }
        }
        return matchMap;
    }
}
